#include <iostream>
#include <vector>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>
#include <random>
#include <chrono>
#include <atomic>

using namespace std;
using namespace chrono;

const int WINDOW_SIZE = 5;
const int PACKET_COUNT = 20;
const double LOSS_PROBABILITY = 0.2;

struct Packet {
    int seqNum;
    bool isAck;
};

class SlidingWindow {
private:
    vector<int> sentAndAcked;
    vector<int> sentNotAcked;
    vector<int> allowedNotSent;
    vector<int> notAllowed;
    int base;
    int nextSeqNum;
    mutex mtx;

public:
    SlidingWindow() : base(0), nextSeqNum(0) {
        allowedNotSent.resize(WINDOW_SIZE);
        for (int i = 0; i < WINDOW_SIZE; ++i)
            allowedNotSent[i] = i;
        notAllowed.resize(PACKET_COUNT - WINDOW_SIZE);
        for (int i = WINDOW_SIZE; i < PACKET_COUNT; ++i)
            notAllowed[i - WINDOW_SIZE] = i;
    }

    bool canSend() {
        lock_guard<mutex> lock(mtx);
        return nextSeqNum < base + WINDOW_SIZE && nextSeqNum < PACKET_COUNT;
    }

    int getNextSeqNum() {
        lock_guard<mutex> lock(mtx);
        return nextSeqNum;
    }

    void sendPacket() {
        lock_guard<mutex> lock(mtx);
        if (nextSeqNum >= PACKET_COUNT) return;

        allowedNotSent.erase(find(allowedNotSent.begin(), allowedNotSent.end(), nextSeqNum));
        sentNotAcked.push_back(nextSeqNum);
        if (nextSeqNum < PACKET_COUNT - 1) {
            notAllowed.erase(notAllowed.begin());
            allowedNotSent.push_back(nextSeqNum + WINDOW_SIZE);
        }
        ++nextSeqNum;
    }

    void receiveAck(int ackNum) {
        lock_guard<mutex> lock(mtx);
        auto it = find(sentNotAcked.begin(), sentNotAcked.end(), ackNum);
        if (it != sentNotAcked.end()) {
            sentNotAcked.erase(it);
            sentAndAcked.push_back(ackNum);
        }

        while (!sentNotAcked.empty() && sentNotAcked.front() == base) {
            ++base;
        }
    }

    void printStatus() {
        lock_guard<mutex> lock(mtx);
        cout << "已发送并收到确认: ";
        for (int seq : sentAndAcked) cout << seq << " ";
        cout << "\n已发送但未收到确认: ";
        for (int seq : sentNotAcked) cout << seq << " ";
        cout << "\n允许发送但尚未发送: ";
        for (int seq : allowedNotSent) cout << seq << " ";
        cout << "\n不允许发送: ";
        for (int seq : notAllowed) cout << seq << " ";
        cout << "\n通知窗口大小: " << WINDOW_SIZE;
        cout << "\n可用窗口大小: " << (base + WINDOW_SIZE - nextSeqNum > 0 ? base + WINDOW_SIZE - nextSeqNum : 0) << endl;
    }
};

class ReceiverWindow {
private:
    vector<int> delivered;
    vector<int> allowedReceive;
    vector<int> notAllowedReceive;
    int expectedSeqNum;
    mutex mtx;

public:
    ReceiverWindow() : expectedSeqNum(0) {
        allowedReceive.resize(WINDOW_SIZE);
        for (int i = 0; i < WINDOW_SIZE; ++i)
            allowedReceive[i] = i;
        notAllowedReceive.resize(PACKET_COUNT - WINDOW_SIZE);
        for (int i = WINDOW_SIZE; i < PACKET_COUNT; ++i)
            notAllowedReceive[i - WINDOW_SIZE] = i;
    }

    bool canReceive(int seqNum) {
        lock_guard<mutex> lock(mtx);
        return find(allowedReceive.begin(), allowedReceive.end(), seqNum) != allowedReceive.end();
    }

    void receivePacket(int seqNum) {
        lock_guard<mutex> lock(mtx);
        if (seqNum == expectedSeqNum) {
            delivered.push_back(seqNum);
            allowedReceive.erase(find(allowedReceive.begin(), allowedReceive.end(), seqNum));
            if (expectedSeqNum < PACKET_COUNT - 1) {
                notAllowedReceive.erase(notAllowedReceive.begin());
                allowedReceive.push_back(expectedSeqNum + WINDOW_SIZE);
            }
            ++expectedSeqNum;
        }
    }

    void printStatus() {
        lock_guard<mutex> lock(mtx);
        cout << "已发送确认并交付主机: ";
        for (int seq : delivered) cout << seq << " ";
        cout << "\n允许接收: ";
        for (int seq : allowedReceive) cout << seq << " ";
        cout << "\n不允许接收: ";
        for (int seq : notAllowedReceive) cout << seq << " ";
        cout << endl;
    }
};

queue<Packet> senderToReceiver;
queue<Packet> receiverToSender;
mutex senderToReceiverMutex;
mutex receiverToSenderMutex;
condition_variable senderToReceiverCV;
condition_variable receiverToSenderCV;
atomic<bool> running(true);

random_device rd;
mt19937 gen(rd());
uniform_real_distribution<> dis(0.0, 1.0);

void senderThread(SlidingWindow& window) {
    while (running) {
        this_thread::sleep_for(seconds(1));

        unique_lock<mutex> lock(senderToReceiverMutex);
        if (window.canSend()) {
            int seqNum = window.getNextSeqNum();
            window.sendPacket();

            if (dis(gen) >= LOSS_PROBABILITY) {
                senderToReceiver.push({seqNum, false});
                senderToReceiverCV.notify_one();
            }
        }
        lock.unlock();

        lock.lock(receiverToSenderMutex);
        while (!receiverToSender.empty()) {
            Packet ack = receiverToSender.front();
            receiverToSender.pop();
            window.receiveAck(ack.seqNum);
        }
        lock.unlock();
    }
}

void receiverThread(ReceiverWindow& window) {
    while (running) {
        unique_lock<mutex> lock(senderToReceiverMutex);
        senderToReceiverCV.wait(lock, []{ return !senderToReceiver.empty() || !running; });
        if (!running) break;

        Packet packet = senderToReceiver.front();
        senderToReceiver.pop();
        lock.unlock();

        if (window.canReceive(packet.seqNum)) {
            window.receivePacket(packet.seqNum);

            if (dis(gen) >= LOSS_PROBABILITY) {
                unique_lock<mutex> ackLock(receiverToSenderMutex);
                receiverToSender.push({packet.seqNum, true});
                receiverToSenderCV.notify_one();
            }
        }
    }
}

void monitorThread(SlidingWindow& senderWindow, ReceiverWindow& receiverWindow) {
    while (running) {
        this_thread::sleep_for(seconds(1));
        cout << "\n===== 窗口状态 =====" << endl;
        senderWindow.printStatus();
        receiverWindow.printStatus();
        cout << "===================" << endl;
    }
}

int main() {
    SlidingWindow senderWindow;
    ReceiverWindow receiverWindow;

    thread sender(senderThread, ref(senderWindow));
    thread receiver(receiverThread, ref(receiverWindow));
    thread monitor(monitorThread, ref(senderWindow), ref(receiverWindow));

    this_thread::sleep_for(seconds(30));
    running = false;

    senderToReceiverCV.notify_one();
    receiverToSenderCV.notify_one();

    sender.join();
    receiver.join();
    monitor.join();

    return 0;
}